package edu.cmu.cs211.snake.util;

import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * This is an implementation of a Queue using a circular array data structure.
 * 
 * The queue is implemented by a wrap-around array
 * we insert to the tail and remove from the head
 * 
 * each time we modify the queue, we update the 2 trackers, head and tail
 * 
 * the access time of poll/offer is O(1)
 * 
 * when the array is full, we initialize another array with bigger size
 * copy all the elements over from head to tail
 * and direct the reference of the old array to the new one
 */
public class ArrayQueue <E> extends AbstractQueue <E> {

	//fields
	private int size;//number of full elements in array
	private int head;//index of first element inserted
	private int tail;//index of last element inserted
	private  Object[] snake;//array implementation of queue
	
	// 16 because it's a power of 2 (do not change this)
	private static final int DEFAULT_SIZE = 16;
	
	/*
	 * Constructor: initialize a new array of default size
	 * initialize size, head and tail to 0's
	 */
	public ArrayQueue () {
		snake = (E[])new Object[DEFAULT_SIZE];
		size = 0;
		head = tail = 0;
		
	}

	// accessor for private field size
	public int size () {
		return size;
	}
	
	/*
	 * Offer: inserts the specified element o into the queue.
	 * 
	 * If size is MAX_INT: can't be larger anymore, we cannot insert, therefore return false
	 * 
	 * Otherwise: insert the element and update the tail counter.
	 * If array is full then resize the array and then insert the new element.
	 * After insertion, return true.
	 */
	public boolean offer (E o)
	{
		if(size == Integer.MAX_VALUE)	// cannot enlarge the array anymore
			return false;
		
		if(size == snake.length)	// array full, need to resize
		{
			Object[] newSnake = (E[]) new Object[size*2];
			
			// copy elements from the old array over starting from head to tail
			int tHead = head;
			for(int i = 0; i < size; i++)
			{
				newSnake[i] = snake[tHead%size];
				tHead++;
			}
			head = 0;
			tail = size;
			snake = newSnake;	// point the reference of the old array to the new array
		}
		
		//insert into array..
		snake[tail] = o;
		tail = (tail +1)%snake.length;	// wrap-around
		size++;
		return true;
	}
	
	/*
	 * poll: dequeue the first element in the queue
	 */
	public E poll ()
	{
		if(size == 0)	// queue is empty 
			return null;
		
		E o = (E)snake[head];
		head = (head+1)%snake.length;	//increment the head counter
		size--;	// update size
		return o;
	}
	
	/*
	 * peek: returns the first element in the queue without modifying the queue
	 */
	public E peek ()
	{
		if(size == 0)	// queue is empty
			return null;
		return (E)snake[head];
		
	}


	/**
	 * <b>NOTE</b>: this iterator does <em>not</em> need fail-fast behavior,
	 * nor does it need to implement remove.
	 */
	public Iterator <E> iterator ()
	{
		return new Iterator<E>()
		{

			private int itrHead =head;	// keeps track of the current element
			private int itrCounter =0;	// keeps track of number of elements traversed
			
			@Override
			public boolean hasNext() {
				return itrCounter < size;
			}

			@Override
			public E next() {
				if(itrCounter < size)
				{
					E o = (E)snake[itrHead%snake.length];
					itrHead++;
					itrCounter++;
					return o;
				}
				throw new NoSuchElementException();
			}

			@Override
			public void remove() {
				 throw new UnsupportedOperationException();
			}
			
		};
	}
}